#include "stdio.h"  /* Usage: dh base exponent modulus */
#include "string.h"

#define bzero(b,len) (memset((b), '\0', (len)), (void) 0)
//#define bzero(b,len) (memset((b), '!0.!', (len)), (void) 0)  
#define bcopy(b1,b2,len) (memmove((b2), (b1), (len)), (void) 0)

typedef unsigned char u;
u m[1024],g[1024],e[1024],b[1024];
int n1,v,d,z1,S=129;
void a(u *x,u *y,int o)
{
	d=0;
	for(v=S;v--;)
		{
			d+=x[v]+y[v]*o;
			x[v]=d;d=d>>8;
		}
}
void s(u *x)
{
	for(v=0;(v<S-1)&&(x[v]==m[v]);)
	v++;
	if(x[v]>=m[v])
	a(x,m,-1);
}

void r(u *x)
{	
	d=0;
	for(v=0;v<S;)
		{
			d|=x[v];
			x[v++]=d/2;
			d=(d&1)<<8;
		}
}

void M(u *x,u *y)
{
	u X[1024],Y[1024];
	bcopy(x,X,S);//bcopy(x,X,S);
	bcopy(y,Y,S);//bcopy(y,Y,S);
	bzero(x,S);//bzero(x,S);
	for(z1=S*8;z1--;)
		{
			if(X[S-1]&1)
				{
					a(x,Y,1);
					s(x);
				}
				r(X);
				a(Y,Y,1);
				s(Y);
		}
}

void h(char *x,u *y)
{
	bzero(y,S);//bzero(y,S);
	for(n1=0;x[n1]>0;n1++)	
		{
			for(z1=4;z1--;)a(y,y,1);
			x[n1]|=32;
			y[S-1]|=x[n1]-48-(x[n1]>96)*39;
		}
}

void p(u *x)
{
	for(n1=0;!x[n1];)n1++;
	for(;n1<S;n1++)printf("%c%c",48+x[n1]/16+(x[n1]>159)*7,48+(x[n1]&15)+7*((x[n1]&15)>9));
	printf("\n");
}

void main1(int c,char **v)
{
	h(v[1],g);
	h(v[2],e);
	h(v[3],m);
	bzero(b,S);//bzero(b,S);
	b[S-1]=1;
	for(n1=S*8;n1--;)
		{
			if(e[S-1]&1)M(b,g);
			M(g,g);
			r(e);
		}
	p(b);
}
